The invention relates to an iterative decoder operative to decode an incoming coded signal with a signal to noise ratio using a sliding window algorithm in which state metrics of a stake are stored for future use as starting points for the backward recursions in a future iteration.
The invention further relates to a method to decode an incoming coded signal with a signal to noise ratio using a sliding window algorithm in which state metrics of a stake are stored for future use as starting points for the backward recursions in a future iteration.
Such an iterative decoder is disclosed by the document ‘Organisation de la memoire dans un turbo decodeur utilisant l' algorithme SUB-MAP’ by Adod Dingninou, Fathi Raouafi and Claude Berrou, Departement d'electronique, ENST Bretagne, BP 832, 29285 Brest Cedex, France.
This document discloses an iterative turbo decoder that uses the sliding window algorithm. In order to decode a data block using the sliding window algorithm, the decoder starts decoding a certain number of trellis steps before and/or after the data block in order to arrive at good estimates of the state metrics of the first and the last state metric vector of the data block. This is possible because of the converging properties of the state metrics in a trellis. Regardless of the assumed starting state metrics the state metrics will converge towards the right solution after several trellis steps as a result of the code used to encode the data word. Thus in a system where 2u states are in a trellis step possible, which form a state metric vector, the turbo decoder starts approximately 5 u trellis steps before and/or 5 u trellis steps after the data block assuring that the state metrics have sufficiently converged to the yield a reasonable estimate of the state metrics at the beginning and end of the data block that is to be decoded. The state metric vectors at the beginning and end of a data block are called stakes. In the sliding window algorithm the 5 u trellis steps before and/or after the data block are calculated for every iteration.
As an improvement over the sliding window algorithm the document ‘Organisation de la memoire dans un turbo decodeur utilisant l' algorithme SUB-MAP’ discloses that is advantageous for an iterative decoder to store the stakes for use in the next iteration.
This increases the memory usage, while reducing the need for starting the trellis 5 u steps outside of the data block resulting in a reduced requirement for processing. This is because the stakes obtained from the previous iteration are already fairly accurate estimates of the states at the beginning and the end of the data block, and a repeated forward and backward recursion started 5 u steps outside the trellis would not produce significantly more accurate estimates of the beginning and end state metrics of the data block. Only the state metrics of the stakes need to be stored.
In a system with 8 states and 10 bits for each metric this results in storage requirements of 80 bits per stake.
For a total of 5000 trellis steps and one stake every 40 trellis steps the memory requirements are 125*8*10=10 Kbit.
A problem of this decoder is that the additional memory requirements are undesirable compared to the regular sliding window algorithm.
The present invention solves this problem by providing a decoder that is characterized in that the state metrics of the stake are compressed using lossy compression.
By compressing the state metrics of the stakes the amount of memory required is further reduced.
This is based on the realization that by using lossy compression some information of the state metrics in the stake is lost, but if the resulting error is comparable to the error resulting from a backward recursion that was started 5 u outside the data, the backward recursion does not suffer from this loss. Consequently there is no need to store the metrics of the states of the stakes loss less.
An embodiment of the present invention is characterized in that the iterative decoder is operative to compress the state metrics by selecting a particular state and storing only the position of the particular state within the stake.
In a trellis step only the relative weights of the various states, which indicate the cost of arriving at that particular state, are relevant. By only storing the position of the most relevant state the storage requirements are greatly reduced. In the above example only 3 bits are needed to store the position of the most relevant state, reducing the memory requirements from 10 Kbit to 125*3=375 bit.
A further embodiment of the present invention is characterized in that the particular state is the state with the lowest cost of all states of the stake.
The most likely state of a stake is associated with the metric that reflects the lowest cost. By only storing the position within a stake of the state with a metric that is associated with the lowest cost, the values of the metrics are lost and the only information remaining is which state in the trellis is most likely. In the above example memory requirements are reduced from 4 Kbit to 125*3=375 bit while the most useful part of the information, the position of the state which is most likely, is retained. This represents a significant reduction in memory requirements while still providing an adequate starting point for a backward recursion.
Yet a further embodiment of the present invention is characterized in that the iterative decoder is operative to reconstruct the stake by assigning a cost of zero to the state of the stake as indicated by the stored position of the particular state, and assigning predetermined, equal, non zero, costs to all other states of the stake.
The reconstruction of the stake is based on the available information, i.e. the position in the stake of the state with a metric representing the lowest cost. The state metrics of the other states are all set to the same value and this reconstructed stake is then used in the next iteration as a starting point for the backward recursion.
Yet a further embodiment of the present invention is characterized in that the predetermined non equal costs are determined by decoding an encoded word in which the encoded word passes through a first state and which encoded word is noise free and selecting a first state metric vector with a state metric equal to zero found for the first decoded state for reconstructing the stake with a state metric equal to zero as indicated by the stored position of the particular state metric
The optimal state metrics to reconstruct the stake are determined by encoding a word and decoding this word while assuring the word is still noise free. When the encoder passes through a state, for instance state 2, in location x while coding the data word, the decoder will find that state 2, at the same location has the lowest cost if the code word is noise free. The state metrics of the state metric vector thus found are associated with, in this example, state 2, and can be regarded as constants and for instance stored in a permanent memory. When a decoder reconstructs a stake where a certain state was indicated by the position that was stored in a previous iteration, that state metric vector stored in the permanent memory is selected that is associated to the same state. For instance the position that was stored during a previous iteration indicates state 2, the decoder reconstructs the stake by retrieving from memory the state metric vector that is associated with state 2 and uses these state metrics in the next iteration.
Yet a further embodiment of the present invention is characterized in that the costs are scaled based on the signal to noise ratio of the incoming signal.
The absolute value of the state metrics of a trellis state reflect the cost of arriving at that state. Therefore, if the signal has a high signal to noise ratio, the likelihood of the states will be more different then when the signal has a low signal to noise ratio. As a consequence the cost to get to a state, as reflected by the state metric, will be more different within a state metric vector for a system with a high signal to noise ratio as well. There will be one state that is clearly more likely in a signal with a high signal to noise ratio, and the cost to arrive at the other possible states will be higher.
In a signal with a low signal to noise ratio none of the states stand out as much more likely and the cost of getting to any state will be similar. Therefore the present invention introduces a scaling factor for the costs, applied to all metrics of all states of the stakes to reflect the signal to noise ratio of the signal.